package com.spring.hot;

/**
 * @author Cizai
 * @since 2022/12/05 10:08
 * @see <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/">...</a>
 **/
public class 在排序数组中查找元素的第一个和最后一个位置 {

    public int[] searchRange(int[] nums, int target) {

        int searchLeft = searchLeft(nums, target);
        int searchRight = searchRight(nums, target);
        if (searchLeft == -2 || searchRight == -2) return new int[] {-1, -1};
        if (searchRight - searchLeft > 1) return new int[]{searchLeft + 1, searchRight - 1};
        return new int[]{-1, -1};
    }

    private int searchLeft(int[] nums, int target) {

        int result = -2;

        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left)/ 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
                result = right;
            }
        }
        return result;
    }

    private int searchRight(int[] nums, int target) {

        int result = -2;

        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left)/ 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
                result = left;
            }
        }
        return result;
    }
}
